#include <iostream>
#include <vector>
using namespace std;

void _MergeSort(vector<int>& nums, vector<int>& tmp, int begin, int end)
{
	if (begin >= end)
		return;
	
	int mid = begin + (end - begin) / 2;
	_MergeSort(nums, tmp, begin, mid);
	_MergeSort(nums, tmp, mid + 1, end);
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;

	int index = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (nums[begin1] < nums[begin2])
		{
			tmp[index++] = nums[begin1++];
		}
		else
		{
			tmp[index++] = nums[begin2++];
		}
	}

	while (begin1 <= end1)
	{
		tmp[index++] = nums[begin1++];
	}

	while (begin2 <= end2)
	{
		tmp[index++] = nums[begin2++];
	}

	for (int i = begin; i <= end; i++)
	{
		nums[i] = tmp[i];
	}
}

void MergeSort(vector<int>& nums)
{
	vector<int> tmp(nums.size());
	_MergeSort(nums, tmp, 0, nums.size() - 1);
}

void CountSort(vector<int>& nums)
{
	int min = 0, max = 0;
	for (auto e : nums)
	{
		if (min > e)
			min = e;

		if (max < e)
			max = e;
	}

	vector<int> tmp(max - min + 1, 0);
	for (size_t i = 0; i < nums.size(); i++)
	{
		tmp[nums[i] - min]++;
	}

	int k = 0;
	for (size_t i = 0; i < tmp.size(); i++)
	{
		while (tmp[i]--)
		{
			nums[k++] = i + min;
		}
	}
}

void MergeSortNoR(vector<int>& nums)
{
	vector<int> tmp(nums.size());
	int gap = 1;
	while (gap < nums.size())
	{
		for (size_t i = 0; i < nums.size(); i += 2*gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;

			if (begin2 >= nums.size())
			{
				break;
			}

			if (end2 >= nums.size())
			{
				end2 = nums.size() - 1;
			}

			int index = i;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (nums[begin1] < nums[begin2])
				{
					tmp[index++] = nums[begin1++];
				}
				else
				{
					tmp[index++] = nums[begin2++];
				}
			}

			while (begin1 <= end1)
			{
				tmp[index++] = nums[begin1++];
			}

			while (begin2 <= end2)
			{
				tmp[index++] = nums[begin2++];
			}

			for (size_t k = i; k <= end2; k++)
			{
				nums[k] = tmp[k];
			}
		}

		gap *= 2;
	}
}

void TestSort()
{
	vector<int> nums = { 1,3,5,7,9,2,4,6,8,10, 0,99 };
	//vector<int> nums = { 1,3,5,7,9,2,4,6,0};
	//MergeSort(nums);
	MergeSortNoR(nums);
	//CountSort(nums);
	for (auto e : nums)
	{
		cout << e << " ";
	}

	cout << endl;
}

int main()
{
	TestSort();
	return 0;
}